package com.LeetCode.dp.String;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * 至少有 k 个重复字符的最长子串
 */
public class LongestDupSubString {




    public int longestSubstring(String s, int k) {
        char[] chars = s.toCharArray();
        HashMap<Character,Integer> map = new HashMap<>();
        for(char c : chars){
            map.put(c,map.getOrDefault(c,0) + 1);
        }
        List<Integer> split = new ArrayList<>();
        for(int i = 0; i<chars.length; i++){
            if(map.get(chars[i]) < k){
                split.add(i);
            }
        }
        if(split.size() == 0) return s.length();
        int ans = 0, left = 0;
        split.add(s.length());
        for(int i = 0; i<split.size(); i++){
            int len = split.get(i) - left;
            if(len > ans) ans = Math.max(ans, longestSubstring(s.substring(left, len),k));
            left = split.get(i) + 1;
        }
        return ans;
    }

    @Test
    public void test(){
        String str = "ababacb";
        System.out.println(longestSubstring(str,3));
    }
}
